package leetcode_600;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *BrickWall_554 计算一根线最小穿过几面墙
 *describe:计算左边往右边累加的数组和 然后用map统计 AC 90%
 *2018年9月13日 下午2:27:29
 */
public class BrickWall_554{
	
	public static void main(String[] args) {
		BrickWall_554 test=new BrickWall_554();
		List<Integer> list1=new ArrayList<Integer>();
		list1.add(1);
		list1.add(2);
		list1.add(2);
		list1.add(1);
		List<Integer> list2=new ArrayList<Integer>();
		list2.add(3);
		list2.add(1);
		list2.add(2);
		List<List<Integer>> wall=new ArrayList<List<Integer>>();
		wall.add(list1);
		wall.add(list2);
		System.out.println(test.leastBricks1(wall));
	}
	
	public int leastBricks(List<List<Integer>> wall) {
		int res=0;
		Map<Integer,Integer> map=new HashMap<Integer,Integer>();
		for(List<Integer> list:wall) {
			int sum=0;
			for(int i=0;i<list.size()-1;++i) {
				sum+=list.get(i);
				Integer now=map.get(sum);
				if(now==null)
					map.put(sum, 1);
				else
					map.put(sum, now+1);
			}
		}
		for(int val:map.values()) {
			res=Math.max(res, val);
		}
		return wall.size()-res;
	}
	
	/**
	 * describe:暴力遍历 直接超时 因为划线是每1米画一条线 但是一条线有10000米那么就做了很多无用功
	 * 2018年9月13日 下午2:11:46 
	 */
	public int leastBricks1(List<List<Integer>> wall) {
        int index[]=new int[wall.size()];
        int min=wall.size();//墙有多少面
        List<Integer> temp=wall.get(0);
        int sum=0;
        for(int i:temp)
        	sum+=i;//计算墙的宽度
        for(int i=1;i<sum;++i) {//开始划线
        	int now=0;
        	for(int j=0;j<wall.size();++j) {
        		List<Integer>list=wall.get(j);
        		int nowV=list.get(index[j]);
        		if(i<nowV) {//穿过了这面墙
        			++now;
        		}
        		else {//否则开始合并
        			++index[j];
        			if(index[j]!=list.size()) {
        				list.set(index[j], list.get(index[j])+nowV);
        			}
        		}
        	}
        	min=Math.min(min, now);
        }
        return min;
    }
}
